// 邻接表
#include <stdio.h>
#include <stdlib.h>

#define MaxVertex 5

typedef char E;

// 节点和头节点分开定义，普通节点记录邻接顶点信息
typedef struct Node{
    int nextVertex;
    struct Node* next;
}* Node;

// 头节点记录元素
struct HeadNode {
    E element;
    struct Node* next;
};

typedef struct TableGraph{
    // 顶点数
    int vertexCount;
    // 边数
    int edgeCount;
    struct HeadNode vertex[MaxVertex];
}* Graph;

Graph create() {
    Graph graph = malloc(sizeof(struct TableGraph));
    // HeadNode可以先不用管
    graph->vertexCount = graph->edgeCount = 0;
    return graph;
}

void addVertex(Graph graph, E element) {
    if(graph->vertexCount >= MaxVertex) return;
    graph->vertex[graph->vertexCount].element = element;
    graph->vertex[graph->vertexCount].next = NULL;
    graph->vertexCount++;
}

void addEdge(Graph graph, int from, int to) {
    // 从头节点开始往后
    Node headNext = graph->vertex[from].next;
    // 创建新节点
    Node newNode = malloc(sizeof (struct Node));
    newNode->nextVertex = to;
    newNode->next = NULL;
    // 如果头节点的下一个没有，则直接连上
    if(!headNext) {
        graph->vertex[from].next = newNode;
    } else { // 否则头节点后已经连上至少一个节点
        do {
            // 如果连上的恰好就是需要添加的那个
            if(headNext->nextVertex == to) {
                return;
            } else if(headNext->next) {
                // 否则继续向后遍历
                headNext = headNext->next;
            } else {
                break;
            }
        } while (1);
        headNext->next = newNode;
    }
    // 此时把边数加 1
    graph->edgeCount++;
}

void printGraph(Graph graph){
    for (int i = 0; i < graph->vertexCount; ++i) {
        printf("%d | %c", i, graph->vertex[i].element);
        Node node = graph->vertex[i].next;
        while (node) {
            printf(" -> %d", node->nextVertex);
            node = node->next;
        }
        putchar('\n');
    }
}

int main() {
    Graph graph = create();
    for (int c = 'A'; c <= 'D' ; ++c)
        addVertex(graph, (char) c);
    addEdge(graph, 0, 1);   //A -> B
    addEdge(graph, 1, 2);   //B -> C
    addEdge(graph, 2, 3);   //C -> D
    addEdge(graph, 3, 0);   //D -> A
    addEdge(graph, 2, 0);   //C -> A

    printGraph(graph);
}